package com.zk.algorithm.factory;

import com.zk.algorithm.bean.BinaryTreeNode;
import com.zk.algorithm.bean.TreeLinkNode;
import com.zk.algorithm.bean.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

public class TreeFactory {

    /**
     * 1 => maxNumber
     *
     * 假设参数为 7，那么构建出来的树为
     *         1
     *      /     \
     *   2          3
     *  /  \       / \
     * 4   5      6   7
     *
     * @param maxNumber
     * @return
     */
    public static BinaryTreeNode buildCompleteTree(int maxNumber) {
        int min = 1;
        BinaryTreeNode root = new BinaryTreeNode(min);

        Queue<BinaryTreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            BinaryTreeNode node = queue.poll();

            int leftVal = node.getVal() * 2;
            if (leftVal > maxNumber) {
                break;
            }

            BinaryTreeNode leftNode = new BinaryTreeNode(leftVal);

            int rightVal = node.getVal() * 2 + 1;
            BinaryTreeNode rightNode = new BinaryTreeNode(rightVal);

            node.setLeft(leftNode);
            node.setRight(rightNode);

            queue.add(leftNode);
            queue.add(rightNode);
        }

        return root;
    }

    public static TreeNode buildTree(Integer[] array) {
        int[] arr = new int[array.length];

        for (int i=0; i<array.length; i++) {
            if (array[i] == null) {
                arr[i] = Integer.MIN_VALUE;
            } else {
                arr[i] = array[i].intValue();
            }
        }

        return buildTree(arr);
    }

    public static TreeLinkNode buildLinkTree(Integer[] array) {
        int[] arr = new int[array.length];

        for (int i=0; i<array.length; i++) {
            if (array[i] == null) {
                arr[i] = Integer.MIN_VALUE;
            } else {
                arr[i] = array[i].intValue();
            }
        }

        return buildLinkTree(arr);
    }

    public static TreeNode buildTree(int[] array) {
        int index = 0;
        int min = array[0];
        TreeNode root = new TreeNode(min);

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();

            if (index + 1 >= array.length) {
                break;
            }
            int leftVal = array[++index];
            if (leftVal != Integer.MIN_VALUE) {
                TreeNode leftNode = new TreeNode(leftVal);
                node.left = leftNode;
                queue.add(leftNode);
            }

            if (index + 1 >= array.length) {
                break;
            }
            int rightVal = array[++index];
            if (rightVal != Integer.MIN_VALUE) {
                TreeNode rightNode = new TreeNode(rightVal);
                node.right = rightNode;
                queue.add(rightNode);
            }
        }

        return root;
    }

    public static TreeLinkNode buildLinkTree(int[] array) {
        int index = 0;
        int min = array[0];
        TreeLinkNode root = new TreeLinkNode(min);

        Queue<TreeLinkNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            TreeLinkNode node = queue.poll();

            if (index + 1 >= array.length) {
                break;
            }
            int leftVal = array[++index];
            if (leftVal != Integer.MIN_VALUE) {
                TreeLinkNode leftNode = new TreeLinkNode(leftVal);
                node.left = leftNode;
                queue.add(leftNode);
            }

            if (index + 1 >= array.length) {
                break;
            }
            int rightVal = array[++index];
            if (rightVal != Integer.MIN_VALUE) {
                TreeLinkNode rightNode = new TreeLinkNode(rightVal);
                node.right = rightNode;
                queue.add(rightNode);
            }
        }

        return root;
    }

}
